package chuan;

import java.util.HashMap;

/**
 * 最长回文子字符串
 *
 */
class huiwenzifuchuan{
    public static String huiwen(String s){
        boolean[][] dp=new boolean[s.length()][s.length()];
        int begin=0;
        int max=0;
        int i,j;
        for(i=0;i<s.length();i++){
            for(j=0;j<=i;j++){

                if(i-j<2){
                    if(s.charAt(i)==s.charAt(j)){
                       dp[j][i]=true;
                    }else{
                        dp[j][i]=false;
                    }
                }
                else{
                    dp[j][i]=(s.charAt(i)==s.charAt(j)&&dp[j+1][i-1]);
                }
                if(dp[j][i]&&i-j+1>max){
                    max=i-j+1;
                    begin=j;
                }
            }
        }
        System.out.println(begin+" "+max);
        return s.substring(begin,begin+max);
    }

    public static void main(String[] args) {
        System.out.println(huiwen("babab"));
    }
}



/**
 * create by Sun
 * 2018/8/15
 * 已知一个字符串，求这个字符串中不包含重复字符的最长子串的长度，如abba返回2，aaaaabc返回3，bbbbbbb返回1
 */
public class nowAndmax {
    private static int test(String s){
        int max=0;
        int begin=0;
        HashMap<Character,Integer> hashMap=new HashMap<>();
        for(int i=0;i<s.length();i++){
            if(hashMap.containsKey(s.charAt(i))){
                /**
                 * 从 重复的下一个开始，最长不过 重复的的地址下一个开始，找begin和 hashmap中（）
                 * 如果从 比较的重复的元素之前开始 那么 再重新来一遍的话，那么最长的长度不会比之前的更长
                 * 比如  bae bcdnm a solkjha
                 * 你从 第一个a的下一个 b开始 再重新到 第三个 a
                 * 如果再从 c开始 那么  用于最长的长度不会 长过 第一个 长度
                 * 那么最长的长度， 所以从 第二个a的下一个开始
                 */
                begin=Math.max(begin,hashMap.get(s.charAt(i))+1);
            }
            if(i-begin+1>max){
                max=i-begin+1;
            }
            hashMap.put(s.charAt(i),i);
        }

        return max;
    }


    public static void main(String[] args) {
        String s="aaaaabc";
        System.out.println(test(s));
    }
}
